public class Solution1799 {

    public int maxScore(int[] nums) {
        int[] f=new int[1<<nums.length];
        int[][] g=new int[nums.length][nums.length];
        for (int i=0;i<nums.length;i++){
            for (int j=0;j<nums.length;j++){
                g[i][j]=gcd(nums[i],nums[j]);
            }
        }
        for (int i=0;i<f.length;i++){
            for (int j=0;j<nums.length;j++){
                for (int k=j+1;k<nums.length;k++){
                    if ((i&(1<<j))!=0 && ((i&(1<<k))!=0)){
                        int s=i^(1<<j)^(1<<k);
                        int p=Integer.bitCount(s);
                        if (p%2==0){
                            f[i]=Math.max(f[i],f[s]+(p/2+1)*g[j][k]);
                        }
                    }
                }
            }
        }
        return f[f.length-1];
    }

    private int gcd(int a, int b) {
        if (a<b){
            int t=a;
            a=b;
            b=t;
        }
        return a%b==0?b:gcd(b,a%b);
    }

    public static void main(String[] args) {
        System.out.println(new Solution1799().maxScore(new int[]{773274,313112,131789,222437,918065,49745,321270,74163,900218,80160,325440,961730}));
    }
}
